package com.hoppinzq.algorithm.tree;

import com.hoppinzq.algorithm.stackAndQueue.MyQueue;

/**
 * 二叉查找树
 * 底层是链表
 * 性质：1、一棵深度为h的二叉树最多有2^(h-1)个叶子节点
 * 2、深度为h的二叉树至多含有2^h-1个节点
 * 完全二叉树有h层，最少有2^(h-1)个节点，最多有2^h-1个节点
 * @param <Key>
 * @param <Value>
 */
public class MyBinaryTree<Key extends Comparable<Key>,Value> {

    private Node root;
    private int N;

    private class Node{
        Node left;
        Node right;
        Key key;
        Value value;

        public Node(Node left, Node right, Key key, Value value) {
            this.left = left;
            this.right = right;
            this.key = key;
            this.value = value;
        }
    }

    //获取树中元素的个数
    public int size() {
        return N;
    }

    public void put(Key key,Value value){
        root=put(root,key,value);
    }

    /**
     * 向指定结点添加键值对
     * @param node
     * @param key
     * @param value
     */
    private Node put(Node node,Key key,Value value){
        //树中没有结点，将传入的结点作为根节点
        if(node==null){
            N++;
            return new Node(null,null,key,value);
        }
        //树中有节点
        int cnp=key.compareTo(node.key);
        if(cnp>0){
            //若传入的节点的key大于传入的key，放到右子树
            node.right=put(node.right,key,value);
        }else if(cnp<0){
            //若传入的节点的key小于传入的key，放到左子树
            node.left=put(node.left,key,value);
        }else{
            //相同就替换
            node.key=key;
            node.value=value;
        }
        return node;
    }

    public Value get(Key key){
        return get(root,key);
    }

    /**
     * 获取指定Key对应的值
     * @param node
     * @param key
     * @return
     */
    private Value get(Node node,Key key){
        //树中没有节点，返回空
        if(node==null){
            return null;
        }
        //对比
        int cnp=key.compareTo(node.key);
        //传入大于节点
        if(cnp>0){
            return get(node.right,key);
        }else if(cnp<0){
            return get(node.left,key);
        }else{
            return node.value;
        }
    }

    private Node getNode(Node node,Key key){
        if(node==null){
            return null;
        }
        int cnp=key.compareTo(node.key);
        if(cnp>0){
            return getNode(node.right,key);
        }else if(cnp<0){
            return getNode(node.left,key);
        }else{
            return node;
        }
    }

    public void delete(Key key){
        delete(root,key);
    }

    /**
     * 树指定节点删除
     * 难点：删除节点后要保持二叉查找树的有序。
     * 1、先找指定节点A。2、找到指定节点A的右子树B，遍历找B树最左边的节点C。3、删除A节点，C节点放到A节点位置
     * @param node
     * @param key
     * @return
     */
    private Node delete(Node node,Key key){
        if(node==null){
            return null;
        }
        //先递归找key对应的节点
        int cnp=key.compareTo(node.key);
        if(cnp>0){
            node.right=delete(node.right,key);
        }else if(cnp<0){
            node.left=delete(node.left,key);
        }else{
            //找到key对应的节点A啦！开始删除操作
            //数量-1
            N--;
            //若A的右子树为空，直接返回左子树成为上一个节点的左子树
            if(node.right==null){
                return node.left;
            }
            //若A的左子树为空，直接返回右子树成为上一个节点的右子树
            if(node.left==null){
                return node.right;
            }
            //若都不为空，遍历找右子树的最左节点，然后与被删除节点替换
            Node tempNode=node.right;
            Node tempParentNode=tempNode;
            while(tempNode.left!=null){
                tempParentNode=tempNode;
                tempNode=tempNode.left;
            }
            tempParentNode.left=null;
            tempNode.left=node.left;
            tempNode.right=node.right;
            node=tempNode;

        }
        return node;
    }

    public Key minKey(){
        return minKey(root).key;
    }
    public Key maxKey(){
        return maxKey(root).key;
    }

    /**
     * 最小的节点，最左边的节点
     * @param node
     * @return
     */
    private Node minKey(Node node){
        while(node.left!=null){
            node=node.left;
        }
        return node;
    }

    /**
     * 最大的节点，最右边的节点
     * @param node
     * @return
     */
    private Node maxKey(Node node){
        while(node.right!=null){
            node=node.right;
        }
        return node;
    }

    //前序遍历
    public MyQueue preErgodic(){
        MyQueue<Integer> queue=new MyQueue<>();
        preErgodic(root,queue);
        return queue;
    }
    private void preErgodic(Node node,MyQueue queue){
        if(node==null){
            return;
        }
        queue.enQueue(node.key);
        preErgodic(node.left,queue);
        preErgodic(node.right,queue);
    }

    //中序遍历
    public MyQueue midErgodic(){
        MyQueue<Integer> queue=new MyQueue<>();
        midErgodic(root,queue);
        return queue;
    }
    private void midErgodic(Node node,MyQueue queue){
        if(node==null){
            return;
        }
        midErgodic(node.left,queue);
        queue.enQueue(node.key);
        midErgodic(node.right,queue);
    }

    //后序遍历
    public MyQueue afterErgodic(){
        MyQueue<Integer> queue=new MyQueue<>();
        afterErgodic(root,queue);
        return queue;
    }
    private void afterErgodic(Node node,MyQueue queue){
        if(node==null){
            return;
        }
        afterErgodic(node.left,queue);
        afterErgodic(node.right,queue);
        queue.enQueue(node.key);
    }

    //层序遍历
    public MyQueue layerErgodic(){
        MyQueue queue=new MyQueue();
        MyQueue tempQueue=new MyQueue();
        if(root!=null){
            queue.enQueue(root.key);
            tempQueue.enQueue(root);
            layerErgodic((Node)tempQueue.deQueue(),queue,tempQueue);
        }else{
            return null;
        }
        return queue;
    }

    private void layerErgodic(Node node,MyQueue queue,MyQueue tempQueue){
        if(node==null){
            return;
        }
        if(node.left!=null){
            tempQueue.enQueue(node.left);
            queue.enQueue(node.left.key);
        }
        if(node.right!=null){
            tempQueue.enQueue(node.right);
            queue.enQueue(node.right.key);
        }
        layerErgodic((Node)tempQueue.deQueue(),queue,tempQueue);
    }

    /**
     * 树最大深度
     * @return
     */
    public int maxDepth(){
        return maxDepth(root);
    }

    private int maxDepth(Node node){
        if(node==null){
            return 0;
        }
        int max=0;
        int maxL = 0,maxR=0;
        if(node.left!=null){
            maxL=maxDepth(node.left);
        }
        if(node.right!=null){
            maxR=maxDepth(node.right);
        }
        max=maxL>maxR?maxL+1:maxR+1;
        return max;
    }

}
